package com.likeycy.my.sort.cmp;

/**
 * @ClassName: MergeSort
 * @Description: 归并排序第一版：重点
 * @Author: sodagreen
 * @Date: 2021/4/3 5:25
 * @Version: 1.0
 */
@SuppressWarnings({"unchecked"})
public class MergeSort<T extends Comparable<T>> extends Sort<T> {

    private T[] leftArray;

    @Override
    protected void sort() {
        leftArray = (T[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的数据进行归并排序
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) {
            return;
        }
        // 在递归中将数组分割成两个子数组
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);

    }

    /**
     * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
     * @param begin
     * @param mid
     * @param end
     */
    private void merge(int begin, int mid, int end) {
        // 左边数组：基于 leftArray
        // li = leftIndex：左边数组的索引； le = leftLength：左边数组的长度；
        int li = 0, le = mid - begin;
        // 右边数组，基于array
        // ri = rightIndex：右边数组的索引； re = rightLength：右边数组的长度；
        int ri = mid, re = end;
        // ai代表要挪到某个下标索引的位置
        int ai = begin;

        // 备份左边数组
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }

        // 开始比较两边的数组大小，挪动元素
        while (li < le) {
            // comparatorToElements比较如果改为 <= 会失去稳定性
            if (ri < re && comparatorToElements(array[li], leftArray[li]) < 0) {
                // 拷贝右边数组到 array。
                array[ai] = array[ri];
                // ai++与ri++可以简化在上一句代码中：例如：array[ai++] = array[ri++]
                ai++;
                ri++;
            } else {
                // 拷贝左边数组到 array
                array[ai] = leftArray[li];
                // ai++与li++可以简化在上一句代码中：例如：array[ai] = leftArray[li]
                ai++;
                li++;
            }
        }
    }


}
